﻿\subsection{Реализация \strlen при помощи SIMD}
\label{SIMD_strlen}

\newcommand{\URLMSDNSSE}{\href{http://go.yurichev.com/17262}{MSDN: MMX, SSE, and SSE2 Intrinsics}}

Прежде всего, следует заметить, что SIMD-инструкции можно вставлять в \CCpp код при помощи специальных 
макросов\footnote{\URLMSDNSSE}. В MSVC, часть находится в файле \TT{intrin.h}.

\newcommand{\URLSTRLEN}{http://go.yurichev.com/17330}

\myindex{\CStandardLibrary!strlen()}
Имеется возможность реализовать функцию \strlen\footnote{strlen() ~--- стандартная функция Си 
для подсчета длины строки} при помощи SIMD-инструкций, работающий в 2-2.5 раза быстрее обычной реализации. 
Эта функция будет загружать в XMM-регистр сразу 16 байт и проверять каждый на ноль

\footnote{Пример базируется на исходнике отсюда: \url{\URLSTRLEN}.}.

\lstinputlisting[style=customc]{patterns/19_SIMD/18_3.c}

Компилируем в MSVC 2010 с опцией \Ox:

\lstinputlisting[caption=\Optimizing MSVC 2010,style=customasmx86]{patterns/19_SIMD/18_4_msvc_Ox_RU.asm}

Как это работает?
Прежде всего, нужно определиться с целью этой ф-ции.
Она вычисляет длину Си-строки, но можно сказать иначе --- её задача это поиск нулевого байта, а затем вычисление его позиции относительно начала строки.

Итак, прежде всего, мы проверяем указатель \TT{str}, выровнен ли он по 16-байтной границе. 
Если нет, то мы вызовем обычную реализацию \strlen.

Далее мы загружаем по 16 байт в регистр \XMM{1} при помощи команды \MOVDQA.

Наблюдательный читатель может спросить, почему в этом месте мы не можем использовать \MOVDQU, 
которая может загружать откуда угодно невзирая на факт, выровнен ли указатель?

Да, можно было бы сделать вот как: если указатель выровнен, загружаем используя \MOVDQA, 
иначе используем работающую чуть медленнее \MOVDQU.

Однако здесь кроется не сразу заметная проблема, которая проявляется вот в чем:

\myindex{Page (memory)}
\newcommand{\URLPAGE}{\href{http://go.yurichev.com/17136}{wikipedia}}

В \ac{OS} линии \gls{Windows NT} (и не только), память выделяется страницами по 4 KiB (4096 байт). 
Каждый win32-процесс якобы имеет в наличии 4 GiB, но на самом деле, 
только некоторые части этого адресного пространства присоединены к реальной физической памяти. 
Если процесс обратится к блоку памяти, которого не существует, сработает исключение. 
Так работает \ac{VM}\footnote{\URLPAGE}.

Так вот, функция, читающая сразу по 16 байт, имеет возможность нечаянно вылезти за границу 
выделенного блока памяти. 
Предположим, \ac{OS} выделила программе 8192 (0x2000) байт по адресу 0x008c0000. 
Таким образом, блок занимает байты с адреса 0x008c0000 по 0x008c1fff включительно.

За этим блоком, то есть начиная с адреса 0x008c2000 нет вообще ничего, т.е. \ac{OS} не выделяла там память. 
Обращение к памяти начиная с этого адреса вызовет исключение.

И предположим, что программа хранит некую строку из, скажем, пяти символов почти в самом конце блока, 
что не является преступлением:

\begin{center}
  \begin{tabular}{ | l | l | }
    \hline
        0x008c1ff8 & 'h' \\
        0x008c1ff9 & 'e' \\
        0x008c1ffa & 'l' \\
        0x008c1ffb & 'l' \\
        0x008c1ffc & 'o' \\
        0x008c1ffd & '\textbackslash{}x00' \\
        0x008c1ffe & здесь случайный мусор \\
        0x008c1fff & здесь случайный мусор \\
    \hline
  \end{tabular}
\end{center}

В обычных условиях, программа вызывает \strlen передав ей указатель на строку \TT{'hello'} 
лежащую по адресу 0x008c1ff8. 
\strlen будет читать по одному байту до 0x008c1ffd, где ноль, и здесь она закончит работу.

Теперь, если мы напишем свою реализацию \strlen читающую сразу по 16 байт, с любого адреса, 
будь он выровнен по 16-байтной границе или нет, 
\MOVDQU попытается загрузить 16 байт с адреса 0x008c1ff8 по 0x008c2008, и произойдет исключение. 
Это ситуация которой, конечно, хочется избежать.

Поэтому мы будем работать только с адресами, выровненными по 16 байт, что в сочетании со знанием 
что размер страницы \ac{OS} также, как правило, выровнен по 16 байт, 
даст некоторую гарантию что наша функция не будет пытаться читать из мест в невыделенной памяти.

Вернемся к нашей функции.

\myindex{x86!\Instructions!PXOR}
\verb|_mm_setzero_si128()| --- это макрос, генерирующий \TT{pxor xmm0, xmm0} ~--- инструкция просто обнуляет регистр \XMM{0}.

\verb|_mm_load_si128()| --- это макрос для \MOVDQA, он просто загружает 16 байт по адресу из указателя в \XMM{1}.

\myindex{x86!\Instructions!PCMPEQB}
\verb|_mm_cmpeq_epi8()| --- это макрос для \PCMPEQB, это инструкция, которая 
побайтово сравнивает значения из двух XMM регистров. 

И если какой-то из байт равен другому, 
то в результирующем значении будет выставлено на месте этого 
байта \TT{0xff}, либо 0, если байты не были равны.

Например:

\begin{verbatim}
XMM1: 0x11223344556677880000000000000000
XMM0: 0x11ab3444007877881111111111111111
\end{verbatim}

После исполнения \TT{pcmpeqb xmm1, xmm0}, регистр \XMM{1} содержит:

\begin{verbatim}
XMM1: 0xff0000ff0000ffff0000000000000000
\end{verbatim}

Эта инструкция в нашем случае, сравнивает каждый 16-байтный блок с блоком состоящим из 16-и нулевых байт, 
выставленным в \XMM{0} при помощи \TT{pxor xmm0, xmm0}.

\myindex{x86!\Instructions!PMOVMSKB}
Следующий макрос \TT{\_mm\_movemask\_epi8()} ~--- это инструкция \TT{PMOVMSKB}.

Она очень удобна как раз для использования в паре с \PCMPEQB.

\TT{pmovmskb eax, xmm1}

Эта инструкция выставит самый первый бит \EAX в единицу, если старший бит первого байта в 
регистре \XMM{1} является единицей. 
Иными словами, если первый байт в регистре \XMM{1} является \TT{0xff}, то первый бит в \EAX будет также единицей, 
иначе нулем.

Если второй байт в регистре \XMM{1} является \TT{0xff}, то второй бит в \EAX также будет единицей. 
Иными словами, инструкция отвечает на вопрос, \q{какие из байт в \XMM{1} являются \TT{0xff}?}
В результате приготовит 16 бит и запишет в \EAX. Остальные биты в \EAX обнулятся.

Кстати, не забывайте также вот о какой особенности нашего алгоритма.

На вход может прийти 16 байт вроде:

\input{patterns/19_SIMD/strlen_hello_and_garbage}

Это строка \TT{'hello'}, после нее терминирующий ноль, затем немного мусора в памяти.

Если мы загрузим эти 16 байт в \XMM{1} и сравним с нулевым \XMM{0}, то в итоге получим такое 
\footnote{Здесь используется порядок с \ac{MSB} до \ac{LSB}.}:

\begin{verbatim}
XMM1: 0x0000ff00000000000000ff0000000000
\end{verbatim}

Это означает, что инструкция сравнения обнаружила два нулевых байта, что и не удивительно.

\TT{PMOVMSKB} в нашем случае подготовит \EAX вот так:\\
\IT{0b0010000000100000}.

Совершенно очевидно, что далее наша функция должна учитывать только первый встретившийся
нулевой бит и игнорировать все остальное.

\myindex{x86!\Instructions!BSF}
\label{instruction_BSF}
Следующая инструкция --- \TT{BSF} (\IT{Bit Scan Forward}). 
Это инструкция находит самый младший бит во втором операнде и записывает его позицию в первый операнд.

\begin{verbatim}
EAX=0b0010000000100000
\end{verbatim}

После исполнения этой инструкции \TT{bsf eax, eax}, в \EAX будет 5, что означает, 
что единица найдена в пятой позиции (считая с нуля).

Для использования этой инструкции, в MSVC также имеется макрос \TT{\_BitScanForward}.

А дальше все просто. Если нулевой байт найден, его позиция прибавляется к тому что 
мы уже насчитали и возвращается результат.

Почти всё.

Кстати, следует также отметить, что компилятор MSVC сгенерировал два тела цикла сразу, для оптимизации.

Кстати, в SSE 4.2 (который появился в Intel Core i7) все эти манипуляции со строками могут быть еще проще:
 \url{http://go.yurichev.com/17331}
